package com.whosly.demo.benchmark.sortalgorithms.insertion;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 插入排序（Insertion Sort）
 *
 * @author fengyang
 * @date 2023/6/12 上午11:09
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class InsertionSort implements ISortingAlgorithms
{
    @Override
    public int[] sorting(int[] arr)
    {
        for (int i = 1; i < arr.length; i++) {
            // 将arr[i]赋给临时变量 val，然后拿 val 这个临时变量和arr[i]之前的元素进行比较
            int val = arr[i];
            int j = i;

            //线性查找 arr[i]应插入的正确位置
            //当 val 这个临时变量比arr[j - 1]要大，那么就说明j后一个元素就是 val， 否则就要将i前面的元素后移
            while (j > 0 && val < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = val;
        }

        return arr;
    }
}
